package _11_整理题目._2_二叉树_递归_dfs_bfs._dfs_路径和;

import org.junit.Test;
import util.TreeNode;

/**
 * 给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。 
 * 
 * 分析：最近公共祖先和o1,o2有三种关系：
 *      1、祖先是o1，o2在祖先左/右侧
 *      2、祖先是o2，o1在祖先左/右侧
 *      3、祖先既不是o1也不是o2，o1,o2分别在祖先左右两侧
 *      
 * 实现：对于二叉树，一般选择递归，递归模板：确定 输入参数和返回值、递归结束条件、递归判断逻辑
 *      递归结束条件：如果当前节点为空 当前节点等于 o1 或等于 o2 就返回当前节点
 *      
 *      递归左子树去找 有目标值的节点
 *      递归右子树去找 有目标值的节点
 *      比较 返回的 左节点 和 右节点
 *      如果left、right都不为空，那么代表o1、o2在root的两侧，所以root为他们的公共祖先
 *      如果left、right有一个为空，那么就返回不为空的那一个节点
 *      
 * https://www.bilibili.com/video/BV1oA411s7xM/
 */
public class _03_两个节点的最近公共祖先 {
    
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        TreeNode result = dfs(root, o1, o2);
        return result.val;
    }
    
    private TreeNode dfs(TreeNode root, int o1, int o2) {
        if (root==null || root.val==o1 || root.val==o2) return root;
        
        TreeNode left = dfs(root.left, o1, o2);
        TreeNode right = dfs(root.right, o1, o2);
        
        if (left != null && right != null) return root;
        return left!=null ? left : right;
    }
    
    @Test
    public void main() {
        Integer[] input = {1, 2, 3, 4, 5, 6, 7};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println(lowestCommonAncestor(root, 2, 3));
        System.out.println(lowestCommonAncestor(root, 4, 5));
    }
    
}
